package com.review.sort;

import java.util.Arrays;

public class MergeSort {
    //归并排序{1,2,3,4,5,6,7,9,10}
    public void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);

        merge(array, start, mid, end);
    }

    public void merge(int[] array, int start, int mid, int end) {//两个有序合并成一个有序

        int a = 0, k = start;//开始位置
        int c = mid - start;//中间位置
        int b = c + 1;//二段开始
        int d = end - start;//结束位置

        int[] clone = new int[d + 1];
        System.arraycopy(array,start,clone,0,d+1);//深拷贝数组,只拷贝用得到的一块数据
        //int[] clone = array.clone();
        /*
        深度拷贝的几种方式：
        https://blog.csdn.net/qq_41207757/article/details/107888794?utm_term=java%E6%95%B0%E7%BB%84%E6%B7%B1%E6%8B%B7%E8%B4%9D&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-0-107888794&spm=3001.4430
        * */
        while (a <= c || b <= d) {
            if (a <= c && b <= d) {
                if (clone[a] > clone[b]) {
                    array[k++] = clone[b];
                    b++;
                } else {
                    array[k++] = clone[a];
                    a++;
                }
            } else if (a <= c) {
                array[k++] = clone[a];
                a++;
            } else {
                array[k++] = clone[b];
                b++;
            }
        }
    }

    public static void main(String[] args) {
        int[] ints = {6, 8, 9, 5, 7, 4, 1, 10, 2, 3};
        //new MergeSort().merge(ints,0,2,4);
        //1,8,6,7,5,9,4,10,2,3,
        new MergeSort().mergeSort(ints, 0, ints.length - 1);
        for (int anInt : ints) {
            System.out.print(anInt + ",");
        }
    }
}
